#include<iostream>
using namespace std;
void insert_sort(int *a,int n);
void insert_sort_d(int *a,int n);
int main()
{
	int a[100];
	for(int i=0;i<100;i++)
		a[i]=i+1;
	a[1]=99;
	a[98]=2;
	insert_sort_d(a,100);
	for(int i=0;i<100;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}
void insert_sort(int *a,int n)
{
	int key;	
	for(int i=1;i<n;i++)
	{
		key=a[i];
		int j=i-1;
		while(j>=0 && a[j]>key)
		{
			a[j+1]=a[j];		
			j--;		
		}
		a[j+1]=key;
		

	}
		
}
void insert_sort_d(int *a,int n)
{
	int key;	
	for(int i=1;i<n;i++)
	{
		key=a[i];	
		int j=i-1;
		while(j>=0 && a[j]<key)
		{
			a[j+1]=a[j];		
			j--;		
		}
		a[j+1]=key;

	}
		
}
